Most personal computer (PC) architecture instruction sets include branch instructions. A branch instruction discontinues a program's execution along a sequential path and causes execution to resume at a new location in memory. The new location is referred to as the target address of the branch. In certain types of PC architectures, the target address for the instruction is stored in one of two architected registers referred to as count and link registers. Three types of branch instructions write to the count or link register; a branch-and-count, a branch-and-link, and a branch-to-link.
A branch-and-count is a branch that decrements the count register upon execution. A branch-and-count is useful for counter dependent loops, such as the statement "FOR i=1 to 100 DO," for example. This statement is executed by loading the count register with value "100" and decrementing the count register by one each time the branch executes until the count register reaches zero.
A branch-and-link is a branch that places the next sequential address following the branch instruction into the link register. A branch-to-link is a branch in which the target address is the value stored in the link register. The branch-and-link and branch-to-link instruction allow simple implementation of subroutine linkages.
After a branch instruction is executed, the contents of the count register or link register may be changed. The updating of the count and link registers creates what is called a write hazard. A write hazard exists when a register is written to and is then meant to be read by another entity, but is written to again before that read can occur. When the read eventually occurs, the register may not contain the correct value for that operation.
The execution of conditional branches is another way in which the contents of the count and link registers may be incorrectly changed. In a conditional branch, control is transferred to the target address depending upon the results of a previous instruction, such as a compare, for example. Conditional branches may be either resolved or unresolved branches depending on whether the result of the previous instruction is known at the time of the execution of the branch.
If the branch is resolved, then it is known whether the branch is to be executed. If the conditional branch is not executed, the next sequential instruction stream immediately following the branch instruction is executed. If the conditional branch is executed, then the instruction stream starting at the target address is executed.
Since it is unknown whether an unresolved branch is to be executed, it is also unknown which instruction stream should be processed. In order to prevent the processor from stalling pending resolution of the unresolved branch, some processors include mechanisms that attempt to predict the outcomes of unresolved branches. Until the outcome of condition is actually executed and the result becomes committed by the processor, the prediction is only speculative. The execution of the predicted instruction stream or path is therefore called speculative execution.
Because updating the count and link register with a speculative value may not be the correct value of the register, conventional processors do not change the architected value of the count and link registers when executing a conditional branch. To overcome write hazards and the potentially corruptive results of speculative execution, conventional processors assign several rename registers to both the count and link registers to backup the contents of the count and rename registers.
When the processor detects that an instruction will alter the contents of the count or link register (e.g., branch-and-count and branch-and-link), the processor saves the original contents of the register in a rename register. If the contents of the count or link register were changed incorrectly due to an incorrect speculative execution, for example, then the count or link register is restored with the value held in the rename register.
When a rename register is written to, it is associated with the instruction that changed the value of the count or link register. Once a rename register for the count or link register is associated with an instruction, the rename register cannot be freed until the instruction has been committed by the processor or an interrupt occurs. If another instruction alters the contents of the count or link register before the first rename register is deallocated, then the contents of the count or link register must be saved in a different rename register. Typically, four rename registers are assigned to the count and link register, respectively.
Although the use of rename registers is useful for restoring the contents of the count and link registers, they have several disadvantages. First, the use of rename registers causes the processor to stall when another branch instruction is encountered and there are no available rename registers to backup the count and link register contents. Therefore, the number of unresolved branches that may be processed without stalling is limited by the number of rename registers allocated to the count and link registers. This degrades processor performance.
In addition, rename registers require the use of a multiplexer when an instruction is encountered that attempts to read the contents of the count or link register. The multiplexer is required to associate the read instruction with the rename register containing the correct result of the count or link register for that particular instruction. Adding additional rename registers to the processor to prevent stalling only increases both the cost and complexity of the processor.
Accordingly, what is needed is a system and method for processing branch instructions that allows multiple branches to be outstanding at the same time and is not limited by the number of rename registers allocated to the count and link registers. The present invention addresses such a need.